package 回溯;

import java.util.LinkedList;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 根据模式串构造最小数字2375.java
 * @createTime 2023年08月24日 14:23:00
 */
public class 根据模式串构造最小数字2375 {
	public String smallestNumber(String pattern) {
		//记录数字 '1' 到 '9'是否已经使用
		boolean[] used = new boolean[10];
		LinkedList<Integer> list = new LinkedList<>();
		backtrack(pattern, list, used, 0);
		StringBuffer ret = new StringBuffer();
		for(int a : list) {
			ret.append(a);
		}
		return ret.toString();
	}

	//回溯函数，start表示当前选择的数是第几个
	public void backtrack(String pattern, LinkedList<Integer> list, boolean[] used, int start) {
		if(list.size() == pattern.length() + 1) {
			return;
		}
		for(int i = 1; i < 10; i++) {
			if(used[i]) {
				continue;
			}
			if(start > 0 && pattern.charAt(start - 1) == 'I' && i < list.getLast()) {
				continue;
			}
			if(start > 0 && pattern.charAt(start - 1) == 'D' && i > list.getLast()) {
				continue;
			}
			list.add(i);
			used[i] = true;
			backtrack(pattern, list, used, start + 1);
			if(list.size() == pattern.length() + 1) {
				return;
			}
			used[list.getLast()] = false;
			list.removeLast();
		}
	}
}
